14. Finite State Machines

A circuit that has 3 parts:

  • Next state circuit
  • Output circuit
  • State register

Basically it's a machine that changes its state and output based on the input and the previous state.
There are two types of FSM:

  • Moore FSM: Only uses current state to choose the output.
  • Mealy FSM: Uses both the current input and the current state to choose the output

Moore FSM

You input, you get into a state, you output the output that corresponds to this state.

Encoded transition tables

Eventually we will have to turn transition tables into equations.
And we will need to represent states into this equation, so we encode the states like this:

  1. Turn the state column into n columns where n are the bits necessary to encode the index of the states. In this case the max index is 3, so 11:
  2. Do the same for output states:
  3. Get the equations:

    It's really trivial here, don't panic. It's just the table read in another way.
    Ask yourself, for each next state column, when is this true, and you literally write the "minterms" for when the column is true.

You an also use one-hot encoding:

Example

Note

This is an example of output table for Moore FSM, useful for comparison with Mealy FSM:

Otherwise we don't really give a damn.

FSM circuit representation

The following diagram is a high level representation of a Moore FSM, we will go into details:

  1. STATE REGISTER: it goes in the middle and holds the current state.

  1. NEXT STATE LOGIC: it selects the next state based on the inputs.

  1. OUTPUT LOGIC: it selects the output based on the current state (in moore fsm).

???

Mealy FSM

In the Moore FSM, the arcs between states indicated the input, now they indicate both input and output:

When you work with Mealy FSM, you need to specify the output table:

Warning

How to solve exercises

From Moore to Mealy

Example

From Mealy to Moore

Input transitions:

Output transitions:

Loop transitions:

Example

Deriving an FSM from a schematic